package leetcode_bin_tree_test;

import bin_tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 剑指 Offer 54. 二叉搜索树的第k大节点
 */
public class KthLargest {
//    static List<Integer> list = new ArrayList<>();
//    static int ret;

    static int count,ret;
    public static int kthLargest(TreeNode root, int k) {
//        if (root == null) {
//            return 0;
//        }
//        // 二叉搜索树
//        // 倒着中序遍历
//        kthLargest(root.right, k);
//        if (!list.contains(root.val)) {
//            list.add(root.val);
//        }
//        if (list.size() == k) {
//            ret = root.val;
//        }
//        kthLargest(root.left, k);
//        return ret;

        // 优化不使用list，使用list还要遍历
        if (root == null) {
            return 0;
        }
        kthLargest(root.right, k);
        if (++count == k) {
            ret = root.val;
        } else if (count < k){
            kthLargest(root.left, k);
        }
        return ret;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(2);
        root.left = node1;
        root.right = node2;
        node1.right = node3;
        System.out.println(kthLargest(root, 1));
    }
}
